package com.yz.shellsort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        //根据数组长度确定h的值，也就是增长量，h=1，循环h=h*2+1，直至h>数组长度/2
        Double[] arr = {5.1, 8.4, 9.8, 4.1, 1.5, 2.3, 3.14, 12.56, 6.18, 7.77, 14.15};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void shellSort(Comparable[] arr) {
        int h = 1;
        while (h < arr.length / 2) {
            h = h * 2 + 1;
        }
        //开始希尔排序
        while (h >= 1) {
            //首先找到要进行插入的位置
            for (int i = h; i < arr.length; i++) {
                //进行插入操作
                for (int j = i; j >= h; j = j - h) {
                    if (SortTools.bigger(arr[j - h], arr[j]))
                        SortTools.exch(arr, (j - h), j);
                    else break;
                }
            }
            //h=h/2
            h = h / 2;
        }
    }
}
